package com.gaogzhen.datastructure.graph.directed;

import edu.princeton.cs.algs4.Digraph;

/**
 *  拓扑排序
 * @author gaogzhen
 */
public class Topological {

    /**
     * 顶点的拓扑排序
     */
    private Iterable<Integer> order;

    /**
     * 顶点在拓扑排序中索引
     */
    private int[] rank;

    /**
     * 构建有向图digraph拓扑排序
     */
    public Topological(Digraph digraph) {
        DirectedCycle finder = new DirectedCycle(digraph);
        if (!finder.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(digraph);
            order = dfs.reversePost();
            rank = new int[digraph.V()];
            int i = 0;
            for (int v : order) {
                rank[v] = i++;
            }
        }
    }

    /**
     * 返回顶点的拓扑排序，没有返回null
     * @return 顶点的拓扑排序，没有返回null
     */
    public Iterable<Integer> order() {
        return order;
    }

    /**
     * 是否可拓扑排序
     * @return {@code true} 可以拓扑排序，同时说明是有向无环图;{@code false}否则
     */
    public boolean hasOrder() {
        return order != null;
    }

    /**
     * 指定顶点v在拓扑排序中索引
     * @param v 指定顶点v
     * @return 顶点v在拓扑排序中索引
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     */
    public int rank(int v) {
        validateVertex(v);
        if (hasOrder()) {
            return rank[v];
        } else {
            return -1;
        }
    }

    /**
     * 校验顶点v是否索引越界
     * @param v 指定顶点
     */
    private void validateVertex(int v) {
        int V = rank.length;
        if (v < 0 || v >= V) {
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
        }
    }
}